﻿#define _CRT_SECURE_NO_WARNINGS
//97.
//学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
//
//排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
//
//给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
//
//返回满足 heights[i] != expected[i] 的 下标数量 。
// 定义⽐较函数（升序）
int cmp_int(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; }
int heightChecker(int* heights, int heightsSize) {
    // 定义⼀个新数组⽤来存储排序后的元素
    int* ans = malloc(heightsSize * sizeof(int));

    // 将heights数组中的元素复制到ans数组中
    memcpy(ans, heights, heightsSize * sizeof(int));
    // for(i=0;i<heightsSize;i++) ans[i]=heights[i];

    // 将ans数组排序
    qsort(ans, heightsSize, sizeof(int), cmp_int);
    int i = 0;
    // 定义变量作为计数器
    int count = 0;

    // 同时遍历两数组
    for (i = 0; i < heightsSize; i++) {
        // 判断两数组中相同位置的元素相同与否
        if (ans[i] != heights[i])
            // 不相同则计数
            count++;
    }

    // 返回计数器的值
    return count;
}